Remove Duplicates from Sorted List || Remove Duplicates from Sorted List II

发表于

Remove Duplicates from Sorted List

Question

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Analysis
  • 在头节点前加result用以保存原本的头节点
  • 将current指针指到存在重复值的最后一个节点，且在循环过程中，须注意current.next不能为空，因为在循环最后的时候还会挪动current
  • 在循环末尾移动pre与current指针
  • 在找到最后一个重复点并赋给current之后，需要将pre.next指向它
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode result=new ListNode(1);
        result.next=head;
        ListNode pre=result;
        ListNode cur=head;
        while(cur!=null){
            while(cur.next!=null&&pre.next.val==cur.next.val){
                cur=cur.next;
            }
            if(pre.next!=cur)
                pre.next=cur;
            pre=pre.next;
            cur=cur.next;
        }
        return result.next;
    }
}

Remove Duplicates from Sorted List II

Question

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis
  • 与I不同的是需要删除所有的重复元素，而非只留一个
  • 步骤均同I，唯一不同的是当找到最后一个重复元素并赋值给current后，pre.next指向的是current.next，除此之外，在pre.next变动之后无需变动pre，因为pre.next已经指向了current.next
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode result=new ListNode(1);
        result.next=head;
        ListNode pre=result;
        ListNode cur=head;
        if(head==null||head.next==null)
            return head;
        while(cur!=null){
            while(cur.next!=null&&pre.next.val==cur.next.val){
                cur=cur.next;
            }
            if(pre.next==cur){  //没有重复，pre后移
                pre=pre.next;
            }else{              //有重复，pre不动，中间删除，pre.next指向新的节点
                pre.next=cur.next;
            }
            cur=cur.next;
        }
        return result.next;
    }
}